// 给定一个单链表的头节点head，要求，将该单链表进行反转，可以迭代或者递归地反转链表

const { LinkedList, ListNode} = require('./64.设计链表')

// 思路1：双指针法，用三个指针，pre，上一个节点，cur，当前处理节点，temp，下一个将处理节点
// 时间复杂度：O(n)
// 空间复杂度：O(1)
function reverseList(head) {
    let pre = null
    let cur = head
    let temp
    while (cur) {
        temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp
    }
    return pre
}

// 思路2：递归，从前往后
// 时间复杂度：O(n)
// 空间复杂度：O(n)

function reverseList2(head) {
    function dfs(pre, cur) {
        if (!cur) {
            return pre
        }
        let temp = cur.next
        cur.next = pre
        return dfs(cur, temp)
    }
    return dfs(null, head)
}

// 思路3：递归，从后往前
// 时间复杂度：O(n)
// 空间复杂度：O(n)

function reverseList3(head) {
    if (!head || !head.next) {
        return head
    }
    let res = reverseList3(head.next)
    // head.next是当前节点的下一个，改变其next,例如{1,2,3,4}，head是3，则head.next是4
    head.next.next = head
    head.next = null
    return res
}

console.log(reverseList((new LinkedList([1, 2, 3, 4])).head));
console.log(reverseList2((new LinkedList([1, 2, 3, 4])).head));
console.log(reverseList3((new LinkedList([1, 2, 3, 4])).head));